package com.mk.web.structure.sort.insertion;

import java.util.Arrays;

/**
 * 直接插入排序
 * Created by WangChen on 2018/12/18 21:38.
 */
public class InsertionSort {

    public static void main(String [] args){
        int[] array = {6, 5, 7, 3, 8, 2};// 1.要排序的数组
        // 执行插入排序
        insertionSort2(array);
        // 输出结果
        System.out.println(Arrays.toString(array));
    }

    /**
     * 稳定的
     * T(n) = O(n²)
     * S(n) = O(1)
     * 基本思想: 将一个待排序 序列 分成两部分, 一部分是已经排好序的(刚开始时, 已经排好的序列为0个元素),
     * 另一部分是待排序的, 没次取出一个待排序元素, 依次从后向前与排好序的序列作比较, 插入到合适的位置.
     * 每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
     *
     * 方法1 与 方法2 的区别是:
     * 方法1 每次比较后，如果前面大于后面的，均交换位置
     * 方法2 是取一个临时变量暂存i的值，向前比较，如果前面的大于i，把前面的元素向后移动, 直到不大于为止, 在当前位置插入i
     *
     * 1. 从第一个元素开始，该元素可以认为已经被排序
     * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 5. 将新元素插入到该位置后
     * 6. 重复步骤2~5
     */
    public static void insertionSort2(int[] array){
//        int tmp;
        for(int i=1;i<array.length;i++){
            int tmp = array[i];  //将当前位置的数给tmp
            int j ;
            for(j = i; j>0 && array[j-1]>tmp; j--){
                /*
                 * 往右移，腾出左边的位置,
                 * array[j-1]>tmp:大于号是升序排列，小于号是降序排列
                 */
                array[j] = array[j-1];
            }
            //将当前位置的数插入到合适的位置
            array[j] = tmp;
        }
    }

    /**
     * 自己写的
     */
    static void insertionSort1(int[] arr){
        for (int i = 1; i <= arr.length -1; i++){
            for (int j = i; j > 0; j--){
                if (arr[j-1] <= arr[j]){// 值相同的元素，不改变位置，是稳定的
                    break;
                }
                int tmp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = tmp;
                System.out.println(arr[j-1] + "<" + arr[j]);
            }
        }
    }
    static void swap(int i, int j){
        if (j < i){
            int tmp = i;
            i = j;
            j = tmp;
        }
        System.out.println(i + "<<<" + j);
    }
}
